home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / polyscan.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  6KB  |  311 lines
  1. /*
  2.  * Copyright 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /* 
  18.  *    polyscan - 
  19.  *        Polygon scanline rendering for characters.
  20.  *
  21.  *      exports:
  22.         void scanoutspan(void(*func)(int y, int x1, int x2))
  23.         void scanoutlinewidth(float width)
  24.         void scanbeginfacet(void)
  25.         void scanendfacet(void)
  26.         void scanvertex(float x, float y)
  27.         void scanbeginscan(void)
  28.         void scanendscan(void)
  29.  *
  30.  *      In general the floating point coordinate 0.0,0.0 maps to
  31.  *      the center of pixel [0,0].  Here is an example of this 
  32.  *    sampling:
  33.  *
  34.  *
  35.  *        scanbeginscan();
  36.  *        scanvertex(-0.5,-0.5);
  37.  *        scanvertex( 0.5,-0.5);
  38.  *        scanvertex( 0.5, 0.5);
  39.  *        scanvertex(-0.5, 0.5);
  40.  *        scanendscan();
  41.  *
  42.  *          Fills pixel [0,0]
  43.  * 
  44.  *            Paul Haeberli - 1992
  45.  */
  46. #include "stdio.h"
  47. #include "math.h"
  48. #include "polyscan.h"
  49.  
  50. #define NBUCKETS    (20)
  51. #define TOLERANCE    (0.0000001)
  52. #define NINCHUNK    (40)
  53.  
  54. typedef struct edge {
  55.     struct edge *next;
  56.     float ymax;
  57.     float ymin;
  58.     float x, y;
  59.     float dxdy;
  60. } Edge;    
  61.  
  62. static void deffillspan(int y,int x1,int x2) 
  63. {
  64.     printf("fillspan y: %d x range: %d to %d inclusive\n",y,x1,x2);
  65. }
  66.  
  67. static Edge *edges, *active, *fedges;
  68. static Edge *buckets[NBUCKETS];
  69. static int npoints;
  70. static Edge start, current, last;
  71. static float outlinewidth = 0.0;
  72. static float xmin, xmax;
  73. static float ymin, ymax;
  74. static float ymin, ymax;
  75. static float ymin, ymax;
  76. static void (*fillspan)(int y, int x1, int x2) = deffillspan;
  77.  
  78. void scanoutspan(void(*func)(int y, int x1, int x2))
  79. {
  80.     fillspan = func;
  81. }
  82.  
  83. static setpix(unsigned int x, unsigned int y)
  84. {
  85.     (fillspan)(y,x,x); 
  86. }
  87.  
  88. static void freeedge(Edge *e)
  89. {
  90.    if( e ) {
  91.        e->next = fedges;
  92.        fedges = e;
  93.    }
  94. }
  95.  
  96. static Edge *newedge(void)
  97. {
  98.     Edge *e;
  99.     int i;
  100.  
  101.     if(!fedges) {
  102.            e = (Edge *)mymalloc(NINCHUNK*sizeof(Edge));
  103.         for(i=0; i<NINCHUNK; i++)
  104.         freeedge(e++);
  105.     }
  106.     e = fedges;
  107.     fedges = fedges->next;
  108.     return e;
  109. }
  110.  
  111. static void createedge(Edge *e1, Edge *e2)
  112. {
  113.     Edge *top, *bot;
  114.     Edge *e, *b;
  115.     int bucketno;
  116.     float xstart, ystart;
  117.     float xend, yend;
  118.     float dy, ady;
  119.  
  120.     if(outlinewidth>0.0) {
  121.     trappixel_callback(setpix);
  122.     subpixline(e1->x-1.0,e1->y,e2->x-1.0,e2->y,outlinewidth);
  123.     }
  124.     if(e1->y>e2->y) {
  125.     top = e1;
  126.     bot = e2;
  127.     } else {
  128.     top = e2;
  129.     bot = e1;
  130.     }
  131.     ady = dy = top->y-bot->y;
  132.     if(ady<0.0)
  133.        ady = 0.0;
  134.     if(ady < TOLERANCE)
  135.     return;
  136.     e = newedge();
  137.     e->ymax = top->y;
  138.     e->ymin = bot->y;
  139.     e->dxdy = (top->x-bot->x)/dy;
  140.     e->x = bot->x;
  141.     e->next = edges;
  142.     edges = e;
  143. }
  144.  
  145. void scanoutlinewidth(float width)
  146. {
  147.     outlinewidth = width;
  148. }
  149.  
  150. void scanbeginfacet(void)
  151. {
  152.     npoints = 0;
  153. }
  154.  
  155. void scanendfacet(void)
  156. {
  157.     if(npoints>0)
  158.     createedge(&last,&start);
  159.     npoints = 0;
  160. }
  161.  
  162. void scanvertex(float x, float y)
  163. {
  164.     x = x+1.0;
  165.     if(npoints++ == 0) {
  166.     start = current;
  167.     start.x = x;
  168.     start.y = y;
  169.     last = start;
  170.     } else  {
  171.     current.x = x;
  172.     current.y = y;
  173.     createedge(&last,¤t);
  174.     last = current;
  175.     }
  176.     if(edges == 0) {
  177.     xmin = xmax = x;
  178.     ymin = ymax = y;
  179.     } else {
  180.     if(x<xmin) xmin = x;
  181.     if(y<ymin) ymin = y;
  182.     if(x>xmax) xmax = x;
  183.     if(y>ymax) ymax = y;
  184.     }
  185. }
  186.  
  187. void scanbeginscan(void)
  188. {
  189.     int i;
  190.  
  191.     edges = NULL;
  192.     active = NULL;
  193.     for(i=0; i<NBUCKETS; i++)
  194.     buckets[i] = NULL;
  195.     scanbeginfacet();
  196. }
  197.  
  198. void scanendscan(void)
  199. {
  200.     Edge *last, *span, *temp, *newspan;
  201.     Edge *b, *e, *ne;
  202.     int i, iy, xchg, x1, x2, scrymin, scrymax;
  203.     float y, ydelta;
  204.  
  205.     scanendfacet();
  206.     if(!edges)
  207.     return;
  208.  
  209.     ydelta = ymax-ymin+0.1;
  210.  
  211. /* insert spans in buckets */
  212.     span = edges;
  213.     while(span) {
  214.     newspan = span->next;
  215.     temp = (Edge *)&buckets[(int)((span->ymin-ymin)*(NBUCKETS-1)/ydelta)];
  216.     y = span->ymin; 
  217.     while(temp->next && (y > temp->next->ymin)) 
  218.         temp = temp->next;
  219.     span->next = temp->next;  
  220.     temp->next = span;  
  221.     span = newspan;
  222.     }
  223.  
  224. /* link buckets together */
  225.     edges = NULL;
  226.     last = (Edge *)&edges;
  227.     for(i=0; i<NBUCKETS; i++) {
  228.     if( (span=buckets[i]) != NULL ) {
  229.         last->next = span;
  230.         while(span->next) 
  231.         span = span->next;
  232.         last = span; 
  233.     }
  234.     }
  235.  
  236. /* scan convert now!! */
  237.     scrymin = floor(ymin);
  238.     scrymax = floor(ymax);
  239.     for(iy=scrymin; iy<=scrymax; iy++) {
  240.     y = iy;
  241.  
  242. /* remove old spans */
  243.     for( span = (Edge *)&active; span->next; )  {
  244.         if (span->next->ymax <= y) {
  245.         temp = span->next;
  246.         span->next = temp->next;
  247.         freeedge(temp);
  248.         } else
  249.         span = span->next;
  250.     }
  251.  
  252. /* add new spans */
  253.     temp = edges;
  254.     while(temp && (temp->ymin <= y)) {
  255.         newspan = temp;
  256.         temp = temp->next;
  257.         if(newspan->ymax > y) {
  258.         newspan->x -= newspan->dxdy * (newspan->ymin - y);
  259.         span = (Edge *)&active; 
  260.         while(span->next && (span->next->x < newspan->x) )
  261.             span = span->next;
  262.         newspan->next = span->next;
  263.         span->next = newspan;
  264.         }
  265.     }
  266.     edges = temp;
  267.  
  268. /* order spans */
  269.     if(active) {
  270.         do {
  271.         xchg = 0;
  272.         span = (Edge *)&active; 
  273.         while(span->next && span->next->next) {
  274.             while(span->next->next ) { 
  275.             if (span->next->x > span->next->next->x) {
  276.                 temp = span->next;
  277.                 span->next = temp->next;
  278.                 temp->next = temp->next->next;
  279.                 span->next->next = temp;
  280.                 xchg++;
  281.             }
  282.             span=span->next;
  283.             }
  284.             span=span->next;
  285.         }
  286.         } while( xchg );
  287.  
  288. /* fill spans */
  289.         for(span=active; span && span->next; span=span->next->next) {
  290.         x1 = span->x; x2 = span->next->x;
  291.         if(x2 > x1)
  292.             fillspan(iy,x1,x2-1);
  293.         }
  294.  
  295. /* increment spans */
  296.         for( span = active; span; span = span->next ) 
  297.         span->x += (span->dxdy);
  298.     }
  299.     }
  300.     while(active) {
  301.     temp = active;
  302.     active = active->next;
  303.     freeedge(temp);
  304.     }
  305.     while(edges) {
  306.     temp = edges;
  307.     edges = edges->next;
  308.     freeedge(temp);
  309.     }
  310. }
  311.